package com.ls.eightSort;


import java.util.ArrayList;

public class QuickSort {

    public static void main(String[] args) {
        int arr[] = {9,8,7,6,5,4,3,2,1};
        SingleQuicksort(arr,0,arr.length-1);
        System.out.println();
    }

    /**
     * 单边快排
     */
    public static void SingleQuicksort(int arr[],int l,int r){
        if (l>r){
            return;
        }
//        int i = partition(arr, l, r);
        int i = doubleQuickSort(arr,l,r);
        // 分而治之
        SingleQuicksort(arr,l,i-1);
        SingleQuicksort(arr,i+1,r);
    }

    /**
     * 双边排序,必须先从右边开始找
     */
    public static int doubleQuickSort(int arr[],int l,int r){
        int pv = arr[l];
        int i = l;
        int j = r;
        while (i<j){
            // 右边找小的
            while (i < j && arr[j]>pv){
                j--;
            }
            // 左边找大的
            while (i < j && arr[i]<=pv){
                i++;
            }

            // 找到位置后，交换
            swap(arr,i,j);
        }

        swap(arr,l,j);
        show(arr);
        return j;

    }


    /**
     * 分区
     */

    public static int partition(int arr[],int l,int r){
        int pv = arr[r];
        // i记录小于pv的临界点 j寻找小于pv
        int i = l;
        for (int j = i; j < r ; j++) {
            if (arr[j]<pv){
                swap(arr,i,j);
                i++;
            }
        }
        swap(arr,i,r);
        show(arr);
        return i;
    }

    public static void swap(int arr[],int l,int r){
        if (l==r){
            return;
        }
        int tem = arr[l];
        arr[l] = arr[r];
        arr[r] = tem;
    }

    public static void show(int arr[]){

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
        System.out.println();
    }


}
